package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}19:09
 */
public class LeetCode409 {
    public int longestPalindrome(String s) {
        int[] cnt = new int[58];// 这里58个字符是因为a~Z之间还有六个特殊的字符，所以多占了六位
        for (char c : s.toCharArray()) {
            cnt[c - 'A'] += 1;
        }
        int ans = 0;
        for (int x: cnt) {
            // 字符出现的次数最多用偶数次。
            ans += x - (x & 1);// 这里&1是因为 当x的个数为奇数的时候，x & 1 = 1;减掉之后就是偶数，偶数怎么都是回文就加上就行了。
        }
        // 如果最终的长度小于原字符串的长度，说明里面某个字符出现了奇数次，那么那个字符可以放在回文串的中间，所以额外再加一。
        return ans < s.length() ? ans + 1 : ans;
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode409().longestPalindrome("abccccdd"));
    }

    public int longestPalindrome2(String s) {
        int[] arr = new int[58];
        // 将所有的字母的个数记录下来
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            arr[aChar - 'A']++;
        }
        int ans = 0;
        // 之后对字符的个数的奇、偶性进行一个判断
        for (int i : arr) {
            if (i != 0){
                ans += i - (i & 1);// 这里&1是因为 当x的个数为奇数的时候，x & 1 = 1;减掉之后就是偶数，偶数怎么都是回文就加上就行了。
            }
        }
        return ans < s.length() ? ans + 1 : ans;// 因为如果小于原来的长度的话就说明是有一个奇数的，那么
    }
}
